/**
 * @file BinarySearchTree.h
 * @author ikun (gitee.com/ikun-ikun)
 * @brief simple design of binary tree template with inheriting relationships
 * @version 0.1
 * @date 2022-11-03
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#ifndef BINARYTREE_H_
#define BINARYTREE_H_
#include<iostream>
using namespace std;
template<typename Comparable>
/**
*A niversal node structure for basic sorts
*of commen BinaryNode class.
*/
class BinaryNode
{
public:
    /**
    *These varibles could be visited by its child class
    */
    virtual Comparable element;  
    virtual BinaryNode *left;
    virtual BinaryNode *right;

    BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
        : element{ theElement }, left{ lt }, right{ rt } { }
        
    BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt )
        : element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
};
template<typename Comparable>
/**
*The special node structure for AVL trees and child of BinaryNode class
*/
class AvlNode:public BinaryNode<Comparable>
{
private:
    AvlNode* left;
    AvlNode* right;
    int height;
public:
    int height;
    AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
      : element{ ele }, left{ lt }, right{ rt }, height{ h } { }
    AvlNode( const Comparable && ele, AvlNode *lt, AvlNode *rt,int h = 0 )
      : element{ std::move(ele) }, left{ lt }, right{ rt },height{h} { }
};

template<typename Comparable>
/**
*base class
*/
class BinaryTree
{
private:
    BinaryNode * root;
public:
    public:
    BinaryTree( ) : root{ nullptr }{}///defult constructor
    ~BinaryTree(){delete root;}///destructor
    /**
    *Functions for basic operations, parameters of which are ruled
    *out for thir pure virtual properties.
    */
    virtual void insert()=0;
    virtual void remove()=0;
    virtual void infixprint()=0;///print the tree with infix output
    
};
template<typename Comparable>
class BinarySearchTree:public BinaryTree<Comparable>
{
private:
    BinaryNode* root;
public:
    BinarySearchTree( ) : root{ nullptr }{}///default constructor
    BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }{}///copy constructor
    BinarySearchTree( BinarySearchTr rhs ) :root { rhs.root }{}///constructor for rvalue reference
    ~BinarySearchTree( );///destructor
    void insert( const Comparable & x );
    void insert( Comparable && x );
    void remove(const Comparable & x);
    /**
    *These three vitual functions are static operations without considerition
    *of parameters, so they could be directly used by the child classes of binary
    *search tree categories 
    */
    virtual void infixprint();///Infix traversal.
    virtual void findMax();///Find the maximum element and output it.
    virtual void findMin();///Find the minimun element and output it.
};

template<typename Comparable>
class AvlNodeTree:public BinarySearchTree<Comparable>
{
private:
    AvlNode* root;
public:
    void insert( const Comparable & x );
    void insert( Comparable && x );
    void remove(const Comparable & x);
    AvlNodeTree( ) : root{ nullptr }{}///default constructor
    AvlNodechTree( const AvlNodeTree & rhs ) : root{ nullptr }{}///copy constructor
    AvlNodeSearchTree( AvlNodeTree && rhs ) : root{ rhs.root }{}///constructor for rvalue reference
    ~AvlNodeSearchTree( );///destructor
private:
    /**
    *Implicit functions for implementation of AvlTree
    */
    void balance(AvlNode * & t);
    void rotateWithLeftChild( AvlNode * & k2 );
    void rotateWithRightChild( AvlNode * & k1 );
    void doubleWithLeftChild( AvlNode * & k3 );
    void doubleWithRightChild( AvlNode * & k1 );
}

#endif